Most image sensors and displays generate or accept image data in color raster scan format. FIG. 1 represents an image being displayed in such a format, in which (horizontal) line 1 is displayed first (the pixels comprising line 1 are displayed sequentially, from left to right), and line 2 is then displayed (the pixels comprising line are 2 displayed sequentially, from left to right), and so on. For a color image, each pixel is typically driven by a set of three analog color component signals. Typically, each analog color component signal is generated by processing a multi-bit digital data word (color component sample) in a digital-to-analog conversion circuit.
In the case that a set of data in color raster scan format represents a monochrome image, the data are said to be in "line-scan" format. In the case that a set of data in color raster scan format represents a color image, the individual color component samples are interleaved.
Conventional color video data in color raster scan format can be interleaved in various different ways. For example, the data can be "pixel interleaved" so that the color component samples within each line are interleaved, or the data can be "line interleaved" so that the color component samples are interleaved on a line-by-line basis. In a frame of line interleaved color raster scan format data, each line of "red" color component samples (each "red" color component sample consisting of a multi-bit word) is followed by a line of "green" color component samples (each "green" color component sample consisting of a multi-bit word), and each line of "green" color component samples is followed by a line of "blue" color component samples (each "blue" color component sample consisting of a multi-bit word).
Throughout this specification, including in the claims, "block" denotes a set of N.times.M samples of a given color component, "word" denotes a color component sample (for example, an eight-bit word defining a red, green, or blue color component sample), "vector" denotes a succession of M words of a single color component that are contiguous on the same line, and "line length" denotes the number of words per line of image data (for the color component having the highest horizontal resolution, in the case of color image data in which the different color components have different resolution). Thus, a block of image data consists of N vectors.
Most image compression algorithms do not process image data in line-scan format, and instead process image data in N.times.M block format. For example, the conventional image compression algorithms known as the ISO "JPEG" algorithm for still images, the CCITT "H.261" recommendation for video conference, and the ISO "MPEG" algorithm for video compression, all process image data in 8.times.8 block format. Each set of block format data processed by such an algorithm is typically a sequence of "minimum coded units" or "MCUs". Each MCU (which can be thought of as a "super block" of a color image) consists of a certain number of blocks for each color component. Since different color components are sometimes sampled with different resolution, the number of blocks per color component in an MCU can vary with the color component (although the blocks for each color component in an MCU all correspond to the same area of the image).
In the case that a sequence of MCUs (i.e., a set of image data in MCU-scan format) represents a monochrome image, the data are said to be in "block-scan" format, and an MCU comprises only one block of data. In the case that data in MCU-scan format represent a color image, blocks of color component samples are interleaved within each MCU.
To implement conventional JPEG, H.261, or MPEG compression, the input data are ideally provided to the image compression processor in minimum coded unit-scan (MCU-scan) format, with each MCU consisting of data in 8.times.8 block format (M=N=8). Examples of such MCU-scan format input data include: a repeating sequence of an 8.times.8 block of red words, followed by an 8.times.8 block of green words, followed by an 8.times.8 block of blue words (image processors for processing "RGB(1:1:1)" images will expect the input data to have this format); and a repeating sequence of two 8.times.8 blocks of Y words, followed by an 8.times.8 block of U words, followed by an 8.times.8 block of V words (image processors for processing "YUV(2:1:1)" images will expect the input data to have this format).
FIG. 2 represents a sequence of blocks of one color component of the image data of FIG. 1, in the order in which such blocks can be asserted to a JPEG image compression processor. Initially, the first eight words from the first line of FIG. 1 are asserted sequentially (from left to right in FIG. 2) as vector 1 of FIG. 2. Then, the first eight words from the second line of FIG. 1 (vector 2 of FIG. 2) are asserted sequentially. Then, the first eight words from the next six lines of FIG. 1 are asserted sequentially (as vectors 3 through 8 of FIG. 2). Next, the second group of eight words from the first line of FIG. 1 are asserted sequentially (as vector 9 of FIG. 2). Thereafter, the second group of eight words from the second line of FIG. 1 are asserted sequentially (as vector 10 of FIG. 2), the second group of eight words from each of the third through eighth lines of FIG. 1 are then asserted sequentially, and so on.
A block diagram of a conventional image compression/decompression system is shown in FIG. 3. The system shown in FIG. 3 receives image data (such as video data from a camera) in color raster scan format, converts the data to MCU-scan format in format converter 20, and performs image compression on the resulting MCU-scan format data in image coding processor 22. The compressed image data asserted at the output of processor 22 are stored or transmitted, and then undergo decompression (inverse-compression) in image decoding processor 24. After undergoing decompression in processor 24, the decompressed data are converted from MCU-scan format to color raster scan format in format converter 26, and the resulting data are displayed (in color raster scan format).
Two types of conventional apparatus for converting image data between color raster scan and MCU-scan formats will next be described with reference to FIGS. 4 and 5. In the apparatus of FIG. 4, memory 32 stores image data whose format is to be converted, and image processor 30 (which performs image compression and/or decompression) supplies address signals for reading data out from, and writing data into, memory 32. In the apparatus of FIG. 5, memory 32 stores image data whose format is to be converted, and micro-controller 34 supplies address signals for writing data into memory 32 and reading format-converted data from memory 32 for subsequent processing by an image processor (not shown in FIG. 5).
In conventional systems of the type shown in FIG. 4 and 5, memory 32 includes two banks of memory. A first strip of data (i.e., N lines of color raster scan data) is read from (or written into) one bank while a second strip of data is written into (or read from) the second bank. For example (during color raster scan to MCU-scan format conversion), the first N lines of color raster scan data can be stored in the first bank of memory 32. Then, while a second set of N lines of color raster scan format data is stored in the second bank, the first strip of data is read from the first bank in MCU-scan format. Then, while a third set of N lines of color raster scan data is stored in the first bank, the second strip of data is read from the second bank in MCU-scan format, and so on.
Major disadvantages of such conventional systems for converting image data between color raster scan and MCU-scan formats include the following: a large capacity memory must be employed (i.e., a memory having capacity to store twice the number of words which comprise each strip of input data, for example, a memory for storing 2N lines of image data where each input data strip comprises N lines); and if such a large capacity memory is implemented as a single memory having two memory banks, the memory must be sufficiently fast to allow both a read access and a write access per word (i.e., the memory access speed must be at least twice the pixel rate, which limits the pixel rate in many applications).
It has been proposed to convert image data from color raster scan format into MCU-scan format in such a manner that only one address is generated per word of the input data. The address is employed to read a previously stored word from a memory location and write a new word into the same memory location.
A similar scheme is proposed in European Patent Application No. 410,909A (published Jan. 30, 1991). EPA 410,909 discloses an apparatus for converting strips of monochrome image data (such as video data) from line-scan format into column-scan format (for example, to convert three input data lines of seven words each, as shown in FIG. 2 of EPA 410,909, into seven three-word columns as shown in FIG. 3 of EPA 410,909).
Although the address generator shown in FIG. 6 of EPA 410,909 is capable of generating a sequence of addresses for reordering a strip of input data in line-scan format into column-scan format, it does so in an inefficient manner. In particular, EPA 410,909 employs a much more complicated apparatus for scan-format conversion than does the present invention, in that EPA 410,909 employs a selection circuit SEL2, an addition circuit S3, and a multiplication circuit which provide input signals to circuit SEL2, to generate coefficients for use in generating the address sequence. This logic circuitry could be eliminated by employing the inventive technique, in which required coefficients for address generation are stored for future use as they become available during an address sequence generation process.